class Solution {
public:
    vector<int> index;
    vector<int> retarr ;
    int tmp1[100000];
    int tmp2[100000];
    vector<int> countSmaller(vector<int>& nums) {
        index.resize(nums.size(),0);
        retarr.resize(nums.size(),0);
        for(int i = 0 ; i < nums.size() ;i ++) index[i] = i;
        mergsort(nums,0,nums.size()-1);
        return retarr;
    }
    void mergsort(vector<int>& nums,int left ,int right){
        if(left >= right ) return ;
        int ret = 0 , middle = (left + right ) >>1;
        mergsort(nums,left,middle);
        mergsort(nums,middle+1,right);
        int cur1 = left,cur2 = middle+1,i=0;
        while(cur1<=middle && cur2 <= right){
            if(nums[cur1] > nums[cur2]){
                retarr[index[cur1]] += right - cur2+1 ;
                tmp1[i] = nums[cur1];
                tmp2[i++] = index[cur1++];
            }else{
                tmp1[i] = nums[cur2];
                tmp2[i++] = index[cur2++];
            }
        }
        while(cur1 <= middle){
            tmp1[i] = nums[cur1];
            tmp2[i++] = index[cur1++];
        }
        while(cur2 <= right){
            tmp1[i] = nums[cur2];
            tmp2[i++] = index[cur2++];
        }
        for(int i = left ; i <= right ; i++){
            nums[i] = tmp1[i-left];
            index[i] = tmp2[i-left];
        }
    }
};